<html>
<head><meta charset="utf-8"><title>overflow evaluating impl on wrapped type · wg-traits · Zulip Chat Archive</title></head>
<h2>Stream: <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/index.html">wg-traits</a></h2>
<h3>Topic: <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/overflow.20evaluating.20impl.20on.20wrapped.20type.html">overflow evaluating impl on wrapped type</a></h3>

<hr>

<base href="https://rust-lang.zulipchat.com">

<head><link href="https://rust-lang.github.io/zulip_archive/style.css" rel="stylesheet"></head>

<a name="185450958"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/overflow%20evaluating%20impl%20on%20wrapped%20type/near/185450958" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jack Wrenn <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/overflow.20evaluating.20impl.20on.20wrapped.20type.html#185450958">(Jan 12 2020 at 21:30)</a>:</h4>
<p>I'm doing a bit of type-level programming, and I've encountered a pattern that consistently seems to make rustc upset. I don't have a good mental model for why this is the case, and I'm hoping someone can shed some light. <a href="https://play.rust-lang.org/?version=nightly&amp;mode=debug&amp;edition=2018&amp;gist=e1f821406912cbf04b0d531117b337d7" target="_blank" title="https://play.rust-lang.org/?version=nightly&amp;mode=debug&amp;edition=2018&amp;gist=e1f821406912cbf04b0d531117b337d7">Playground link.</a></p>
<p>Let's say we define a type-level non-empty list, and a predicate <code>Contains&lt;E&gt;</code> that's satisfied if the type <code>E</code> appears in the list:</p>
<div class="codehilite"><pre><span></span><span class="k">struct</span> <span class="nc">One</span><span class="o">&lt;</span><span class="n">H</span><span class="o">&gt;</span><span class="p">{}</span><span class="w"></span>
<span class="k">struct</span> <span class="nc">Cons</span><span class="o">&lt;</span><span class="n">H</span><span class="p">,</span><span class="w"> </span><span class="n">T</span><span class="o">&gt;</span><span class="p">{}</span><span class="w"></span>

<span class="cp">#[marker]</span><span class="w"></span>
<span class="k">trait</span><span class="w"> </span><span class="n">Contains</span><span class="o">&lt;</span><span class="n">Needle</span><span class="o">&gt;</span><span class="p">{}</span><span class="w"></span>

<span class="sd">/// The needle is the only element of the list.</span>
<span class="k">impl</span><span class="o">&lt;</span><span class="n">H</span><span class="o">&gt;</span><span class="w"> </span><span class="n">Contains</span><span class="o">&lt;</span><span class="n">H</span><span class="o">&gt;</span><span class="w"> </span><span class="k">for</span><span class="w"> </span><span class="n">One</span><span class="o">&lt;</span><span class="n">H</span><span class="o">&gt;</span><span class="w"> </span><span class="p">{}</span><span class="w"></span>

<span class="sd">/// The needle is the first element of the list.</span>
<span class="k">impl</span><span class="o">&lt;</span><span class="n">H</span><span class="p">,</span><span class="w"> </span><span class="n">T</span><span class="o">&gt;</span><span class="w"> </span><span class="n">Contains</span><span class="o">&lt;</span><span class="n">H</span><span class="o">&gt;</span><span class="w"> </span><span class="k">for</span><span class="w"> </span><span class="n">Cons</span><span class="o">&lt;</span><span class="n">H</span><span class="p">,</span><span class="w"> </span><span class="n">T</span><span class="o">&gt;</span><span class="w"> </span><span class="p">{}</span><span class="w"></span>

<span class="sd">/// The needle is in the tail of the list.</span>
<span class="k">impl</span><span class="o">&lt;</span><span class="n">E</span><span class="p">,</span><span class="w"> </span><span class="n">H</span><span class="p">,</span><span class="w"> </span><span class="n">T</span><span class="o">&gt;</span><span class="w"> </span><span class="n">Contains</span><span class="o">&lt;</span><span class="n">E</span><span class="o">&gt;</span><span class="w"> </span><span class="k">for</span><span class="w"> </span><span class="n">Cons</span><span class="o">&lt;</span><span class="n">H</span><span class="p">,</span><span class="w"> </span><span class="n">T</span><span class="o">&gt;</span><span class="w"></span>
<span class="k">where</span><span class="w"> </span><span class="n">T</span>: <span class="nc">Contains</span><span class="o">&lt;</span><span class="n">E</span><span class="o">&gt;</span><span class="w"></span>
<span class="p">{}</span><span class="w"></span>
</pre></div>


<p>This works totally fine, as expected.</p>
<p><strong>BUT</strong>, if we wrap each of the above types in another type, the compiler overflows evaluating the requirement <code>Wrap&lt;One&lt;_&gt;&gt;: Contains&lt;Wrap&lt;_&gt;&gt;</code>:</p>
<div class="codehilite"><pre><span></span><span class="k">struct</span> <span class="nc">Wrap</span><span class="o">&lt;</span><span class="n">T</span><span class="o">&gt;</span><span class="p">(</span><span class="n">T</span><span class="p">);</span><span class="w"></span>

<span class="sd">/// The needle is the only element of the list.</span>
<span class="k">impl</span><span class="o">&lt;</span><span class="n">H</span><span class="o">&gt;</span><span class="w"> </span><span class="n">Contains</span><span class="o">&lt;</span><span class="w"> </span><span class="n">Wrap</span><span class="o">&lt;</span><span class="n">H</span><span class="o">&gt;</span><span class="w"> </span><span class="o">&gt;</span><span class="w"> </span><span class="k">for</span><span class="w"> </span><span class="n">Wrap</span><span class="o">&lt;</span><span class="w"> </span><span class="n">One</span><span class="o">&lt;</span><span class="n">H</span><span class="o">&gt;</span><span class="w"> </span><span class="o">&gt;</span><span class="w"> </span><span class="p">{}</span><span class="w"></span>

<span class="sd">/// The needle is the first element of the list.</span>
<span class="k">impl</span><span class="o">&lt;</span><span class="n">H</span><span class="p">,</span><span class="w"> </span><span class="n">T</span><span class="o">&gt;</span><span class="w"> </span><span class="n">Contains</span><span class="o">&lt;</span><span class="w"> </span><span class="n">Wrap</span><span class="o">&lt;</span><span class="n">H</span><span class="o">&gt;</span><span class="w"> </span><span class="o">&gt;</span><span class="w"> </span><span class="k">for</span><span class="w"> </span><span class="n">Wrap</span><span class="o">&lt;</span><span class="w"> </span><span class="n">Cons</span><span class="o">&lt;</span><span class="n">H</span><span class="p">,</span><span class="n">T</span><span class="o">&gt;</span><span class="w"> </span><span class="o">&gt;</span><span class="w"> </span><span class="p">{}</span><span class="w"></span>

<span class="sd">/// The needle is in the tail of the list.</span>
<span class="k">impl</span><span class="o">&lt;</span><span class="n">E</span><span class="p">,</span><span class="w"> </span><span class="n">H</span><span class="p">,</span><span class="w"> </span><span class="n">T</span><span class="o">&gt;</span><span class="w"> </span><span class="n">Contains</span><span class="o">&lt;</span><span class="w"> </span><span class="n">Wrap</span><span class="o">&lt;</span><span class="n">E</span><span class="o">&gt;</span><span class="w"> </span><span class="o">&gt;</span><span class="w"> </span><span class="k">for</span><span class="w"> </span><span class="n">Wrap</span><span class="o">&lt;</span><span class="w"> </span><span class="n">Cons</span><span class="o">&lt;</span><span class="n">H</span><span class="p">,</span><span class="n">T</span><span class="o">&gt;</span><span class="w"> </span><span class="o">&gt;</span><span class="w"></span>
<span class="k">where</span><span class="w"> </span><span class="n">Wrap</span><span class="o">&lt;</span><span class="n">T</span><span class="o">&gt;</span>: <span class="nc">Contains</span><span class="o">&lt;</span><span class="w"> </span><span class="n">Wrap</span><span class="o">&lt;</span><span class="n">E</span><span class="o">&gt;</span><span class="w"> </span><span class="o">&gt;</span><span class="w"></span>
<span class="p">{}</span><span class="w"></span>
</pre></div>


<p>Why does this happen? Is there a name for what's going on here? What causes the type checker to start recursively enumerating types?</p>



<hr><p>Last updated: Aug 07 2021 at 22:04 UTC</p>
</html>